import java.lang.*;
import java.util.*;

/**
 * Binary Search Tree Implementation.
 * No Duplicates allowed.
 **/

public class BinarySearchTreeIterative {

	private Node root = null;

	private class Node {
		Integer value = null;
		Node left = null;
		Node right = null;
		Node parent = null;
		boolean isDone = false;
		Node(Integer val) {
			value = val;
		}
	}

	public void add(Integer ele){
		if(root == null){
			root = new Node(ele);
			root.parent = null;
		}else{
			Node t = root;
			while(true){
				if(ele > t.value){
					if(t.right == null){
						t.right = new Node(ele);
						t.right.parent = t;
						break;
					}else if (t.right.value == ele){
						break;
					}else{
						t = t.right;
					}
				} else if(ele < t.value){
					if(t.left == null){
						t.left = new Node(ele);
						t.left.parent = t;
						break;
					}else if(t.left.value == ele){
						break;
					}else{
						t = t.left;
					}
				}else{
					break;
				}

			}
		}
	}

	public Integer getXthLargest(int pos) {
		Node t = root;
		int count = 0;
		while(true) {
			if(t.right != null && !t.right.isDone){
				t = t.right;
			}else{
				if(!t.isDone){
					if(++count == pos) return (t.value);
					t.isDone = true;
					if(t.right == null || t.right.isDone){
						if(t.left != null) t = t.left; else if(t.parent != null) t = t.parent; else break; 
					}else{ 
						if(t.parent != null) t = t.parent; else break; 
					}
				}else{
					if(t.parent != null) t = t.parent; else break;
				}
			}
		}
		return null;
	}


	public static void main(String[] args){
		if(args.length != 2) {
			throw new IllegalArgumentException("Provide value for k, the k(th) largest element in the Binary Tree AND Number of elements to be generated.");
		}

		int index = -1;
		int noOfEle = -1;

		try {
			index = Integer.parseInt(args[0]);
			noOfEle = Integer.parseInt(args[1]);
			if (index < 1) {
				throw new IllegalArgumentException("Index cannot be less than 1");
			}
			if(noOfEle < 1){
				throw new IllegalArgumentException("Number of elements for Binary Search Tree should be greater than 0.");
			}
		}catch (Exception e){
			throw new IllegalArgumentException("Illegal Argument. Could not parse the argumrnt to type integer.");
		}


		BinarySearchTreeIterative bst = new BinarySearchTreeIterative();
		Random rnd = new Random(4);
		System.out.println("Numbers are added in order:");
		for(int k = 0; k < noOfEle; ++k) {
			int toAdd = rnd.nextInt(noOfEle)*rnd.nextInt(noOfEle)*rnd.nextInt(noOfEle);
			System.out.println((k+1) + "\t-->\t" + toAdd);
			bst.add(toAdd);
		}	       
		Integer xthL = bst.getXthLargest(index);
		if(xthL != null)
			System.out.println(index + " Largest Element Is: " + xthL);
		else
			System.out.println("Index position exceeded number of elements.");

	}
}
